Ensuring communication security in complex computer networks is well known to be one of the central challenges of most information and communication technology (ICT) applications, which has resulted in an increased interest for the field of cryptography over the last years. For example, cryptographic encryption (i.e. the process of rendering information unreadable to unauthorized parties) has become of fundamental importance in a myriad of different applications ranging from electronic transactions to military data transmission. The security of a given encryption technique relies on the crucial assumption that users have access to secret keys. A secret key consists in a sequence of genuine random numbers that is equiprobable and unpredictable. Typically, a secret key is processed with the information to protect using an algorithm that renders the result indecipherable, up to an arbitrarily small level, to anyone not in possession of the given key. The origin of the key is central to the security of the data to protect since any information on the source of the key is a liability. A common way to generate secret keys is to use a random number generator (RNG).
A fundamental requirement for random number generation is the ability to produce random sequences that have a uniform probability distribution. In other words, it is the ability to generate numbers with equal probability. Accordingly, a measure of RNG quality in this regard is that it has a small bias, i.e. a small difference between the probability distribution of the RNG output and the uniform probability distribution. Random physical phenomena employed in implementing hardware RNGs pose unique problems in terms of harnessing the phenomena to provide, as digital signals, the needed uniformly distributed random numbers.
A second fundamental requirement for random number generation is the ability to produce actual randomness. Strictly speaking, it is the ability to generate unpredictable numbers, since any correlation among the generated numbers is detrimental. However, today's known random physical phenomena useful for providing genuine random numbers limit the generation rate because of their slowly varying characteristics. For several cryptographic tasks, this crucial point makes physical random number generation unappealing. One widely practiced alternative is to circumvent this problem by replacing uniformly distributed genuine RNGs by uniformly distributed pseudo RNGs.
RNGs thus provide in two distinct categories: pseudo-random number generators (PRNGs) and hardware (or physical) random number generators (HRNGs). A PRNG is a deterministic algorithm for generating a sequence of uniformly distributed numbers that only approximates the properties of genuine random numbers. The sequence is not truly random in that it is completely determined by a relatively small set of initial parameters and eventually repeats due to the finiteness of the computer on which it is running. To initialize a sequence, the algorithm employs an internal state of the computer (called a seed) such as current time, mouse movement or keyboard strokes. The algorithm will always produce the same sequence thereafter when initialized with the same seed. Even though the finite period of certain PRNGs can be very long, this resource becomes meaningless in a cryptographic context if an untrusted third party can correctly guess the PRNG algorithm as well as the initial seed used to generate a secret key.
Generally, pseudo-random numbers are generated by deterministic algorithmic processes such as modular multiplication, which, by careful selection of parameters, yield numbers that are devoid of obvious patterns. Because no physical phenomenon is involved, all elements of pseudo-random sequences are, necessarily, causally related and the sequences may be accurately predicted and replicated. This replication property is fundamental for pseudo-random applications such as the RC4 stream cipher cryptosystem, in which the sender uses a PRNG to encrypt information to be sent and the recipient uses the exact same PRNG to regenerate the sender's plaintext. However, for random number applications, this replication property is a liability, since, for example, in order to maximize security, RSA keys (i.e. exponents and modulus) are generated exclusively by random means.
A cryptographically safer alternative in generating secret keys is to use a HRNG. A HRNG is an apparatus that generates uniformly distributed random numbers from a physical process. Such devices are often based on physical systems such as thermal noise, avalanche noise, or time drift. Although they are described, in principle, by deterministic (and therefore predictable) laws of physics these systems typically contain such high degrees of complexity that they are in practice difficult to simulate. However, HRNGs suffer a major drawback that is the rate at which they can generate random numbers. Most physical systems harnessed to produce secret keys generate numbers at rates that are often a few orders of magnitude smaller than what is required in several cryptographic situations such as those encountered by financial or banking institutions. For this reason, security technicians often resort to using the less secure but faster PRNGs.
HRNGs can be divided in three categories depending on the nature of the physical phenomena used as the source of randomness. HRNGs of the first category are based on macroscopic phenomena and extract their randomness from our inability to properly monitor the evolution of a macroscopic system. A simple example of such macroscopic HRNG entails the roll of six faced dices. These HRNGs are typically very slow and, in theory, completely predictable as macroscopic systems obey the deterministic laws of classical physics.
A second category of HRNGs is based on deterministic phenomena of microscopic origin. These HRNGs extract their randomness from our inability to properly monitor the evolution of a microscopic system. Although the constituents of the system are generally of quantum nature (electrons or photons), the processes used as the source of randomness are classical and in principle predictable. All the uncertainty lies in our inability to characterize the quantum system properly, not in the quantum nature of the system itself. In the language of quantum mechanics, the classical nature of these systems is characterized by the use of mixed states rather than pure states.
Several prior art HRNGs of the first and second category generate random time periods as means to randomly generate numbers. Examples include a so-called “electronic roulette wheel”, and a method involving radioactivity by which Random-numbers modulo-M are produced by stopping the rapidly advancing (modulo-M) counter at the random time, determined by an electron arrival of the Geiger-Mueller tube (from a sample of strontium 90). Another recent method in this regard employs user actions such as keystrokes, as means to randomly select numbers from software counters in order to generate secret keys or seeds for PRNGs. The generation rates provided by the former method are obviously much higher than those provided by the latter method, but the rates are nevertheless much smaller than 1 Mbit/sec.
Further prior art HRNGs solutions of the second category use deterministic means to distort random electronic noise, which is normally distributed, in order to provide a 1-bit random variable. One example subjects the noise to successive stages of clipping, amplifying, and sample, whereby the normal distribution is thus directly divided in two, with the probability of each fraction mapped to one of the two possible digits. Another example uses a comparator to severely amplify the difference between the instantaneous output of two sources. In practice, locking the division point at the median in the former example, or locking the two medians in the latter example, within a tolerance that avoids a bias, requires extreme precision and periodic calibration.
Even further prior art solutions of the second category use thermal noise as means to generate random numbers. HRNGs based on this phenomena are vulnerable to attack by lowering the temperature of the system, though most systems will stop operating at temperatures (e.g. 150° K.) low enough to reduce noise by a factor of two. They also suffer from a low generation rate. Some of the thermal phenomena include thermal amplified noise from a resistor, avalanche noise generated from an avalanche diode, atmospheric noise, detected by a radio receiver attached to a computer. As for all HRNGs of the second category, thermal noise is, in principle, deterministic, rendering the random numbers, in principle, predictable.
In comparison with deterministic physics, quantum physics is fundamentally random. It is the only theory within the fabric of modern physics that integrates randomness. It is thus a natural choice to take advantage of this intrinsic randomness and to resort to the use of a quantum process as source for HRNGs. HRNGs of the third category are thus based on true quantum phenomena and extract their randomness from the uncertainty lying at the heart of quantum mechanics.
Recent prior art solutions of this category exploit strongly attenuated coherent pulses consisting on average of a single photon travelling through a semi-transparent mirror. The mutually exclusive events, reflection and transmission, are detected and associated to one of a binary outcome. Although the resulting random sequences are indeed uniformly distributed and unpredictable, this solution remains very slow (e.g. 1 Mbit/sec) because of the slow single-photon avalanche photodetectors needed to measure attenuated light pulses.
U.S. Pat. No. 7,284,024 describes a different approach to a quantum random number generator system that employs quantum noise from an optical homodyne detection apparatus. The system utilizes the quantum noise generated by splitting a laser light signal using a beam splitter having four ports, one of which receives the laser light signal, one of which is connected to vacuum and two of which are optically coupled to photodetectors. Such a system effectively measures the random fluctuations of the vacuum entering the second port of the beam splitter. Processing electronics process the signal derived from subtracting the two photodetector signals to create a random number sequence. The idea is that the difference signal associated with the two photodetectors should be truly random, such that the system is a true random number generator.
In order to operate effectively, such a homodyne detection system requires two identical photodetectors. In the case of non-identical photodetectors (which in practice is likely to be the case), a bias is introduced into the random number generation.
Moreover, maintaining the two photodiodes identical during operation is difficult because of temperature and current fluctuations that may occur independently in both detectors. It is thus problematic to render this system stable and robust. As far as the inventors are aware, the system described in U.S. Pat. No. 7,284,024 has not been put into commercial production.
It is believed that the limitations of the prior art methods and means have resulted in speed and randomness constraints on execution of random number applications that cannot tolerate pseudo-random characteristics such as cryptographic key generation. These limitations have resulted in the use of faster but riskier PRNGs. Consequently, there is a need in the art for a method and means that provide uniformly distributed, genuinely unpredictable, random number sequences, using simpler and more reliable equipment, and providing faster rates.